from typing import List


class SegmentTreeForMin:
    """求最小值线段树"""

    class _Node:
        """线段树结点"""
        __slots__ = "start", "end", "val", "left", "right", "lazy"

        def __init__(self, start, end):
            self.start = start  # 左侧边界（包含）
            self.end = end  # 右侧边界（包含）
            self.left = None  # 结点左子结点
            self.right = None  # 结点右子节点
            self.val = float("inf")  # 当前结点最小值
            self.lazy = float("inf")  # 懒惰计算标签（即未计算的子结点最小值）

    def __init__(self, size):
        """初始化线段树实例"""
        self.root = self._Node(0, size)

    def _update(self, node, pos1, pos2, data):
        """更新数据"""
        # 当前区间正好为当前结点的情况：即不需要继续分裂的情况
        if node.start == pos1 and node.end == pos2:
            node.val = min(node.val, data)
            node.lazy = min(node.lazy, data)

        # 当前区间为当前结点的部分的情况：即需要继续分裂的情况
        else:
            mid = (node.start + node.end) // 2

            # 创建两个子结点
            if node.left is None:
                node.left = self._Node(node.start, mid)
            if node.right is None:
                node.right = self._Node(mid + 1, node.end)

            # 下推当前结点的懒惰计算标签
            if node.lazy != float("inf"):
                node.left.val = min(node.left.val, node.lazy)
                node.left.lazy = min(node.left.lazy, node.lazy)
                node.right.val = min(node.right.val, node.lazy)
                node.right.lazy = min(node.right.lazy, node.lazy)
                node.lazy = float("inf")

            # 更新当前结点的子结点
            node.val = min(node.val, data)
            if pos2 <= mid:
                self._update(node.left, pos1, pos2, data)
            elif pos1 >= mid + 1:
                self._update(node.right, pos1, pos2, data)
            else:
                self._update(node.left, pos1, mid, data)
                self._update(node.right, mid + 1, pos2, data)

    def _query(self, node, start, end):
        """查询数据"""
        # 当前区间正好为当前结点的情况：即不需要继续分裂的情况
        if node.start == start and node.end == end:
            return node.val

        # 当前结点没有子结点的情况：即当前结点下所有位置的结果一致的情况
        elif node.left is None and node.right is None:
            return node.val

        # 当前区间为当前结点的部分的情况：即需要继续分裂的情况
        else:
            mid = (node.start + node.end) // 2

            # 创建两个子结点
            if node.left is None:
                node.left = self._Node(node.start, mid)
            if node.right is None:
                node.right = self._Node(mid + 1, node.end)

            # 下推当前结点的懒惰计算标签
            if node.lazy != float("inf"):
                node.left.val = min(node.left.val, node.lazy)
                node.left.lazy = min(node.left.lazy, node.lazy)
                node.right.val = min(node.right.val, node.lazy)
                node.right.lazy = min(node.right.lazy, node.lazy)
                node.lazy = float("inf")

            # 查询当前结果的最小值
            if end <= mid:
                return self._query(node.left, start, end)
            elif start >= mid + 1:
                return self._query(node.right, start, end)
            else:
                return min(self._query(node.left, start, mid),
                           self._query(node.right, mid + 1, end))

    def update_one(self, query, data):
        self._update(self.root, query, query, data)

    def update_range(self, start, end, data):
        self._update(self.root, start, end, data)

    def query_one(self, query):
        return self._query(self.root, query, query)

    def query_range(self, start, end):
        return self._query(self.root, start, end)


class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        # 坐标压缩
        index = set([i1 for i1, i2 in intervals] + [i2 for i1, i2 in intervals] + queries)
        index = {idx: i for i, idx in enumerate(sorted(index))}

        st = SegmentTreeForMin(len(index) + 1)
        for left, right in intervals:
            st.update_range(index[left], index[right], right - left + 1)

        ans = []
        for query in queries:
            now = st.query_one(index[query])
            ans.append(now if now != float("inf") else -1)

        return ans


if __name__ == "__main__":
    print(Solution().minInterval(intervals=[[1, 4], [2, 4], [3, 6], [4, 4]], queries=[2, 3, 4, 5]))  # [3,3,1,4]
    print(Solution().minInterval(intervals=[[2, 3], [2, 5], [1, 8], [20, 25]], queries=[2, 19, 5, 22]))  # [2,-1,4,6]

    # 测试用例13:[11,21,12,4,4,6,12,10,12,1,11,21,10,21,1,14,1,4,11,1,6,6,7,10,7,14,21,7,11,7,11,4,3,1,21,21,7,10,12,21,12,7,6,21,21,3,11,14,7,21,12,6,14,6,6,12,21,21,6,21,21,10,6,12,12,11,1,1,7,11,80,7,6,12,1,12,6,3,6,6,12,10,10,12,1,1,10,14,11,6,21,14,21,10,11,6,3,1,11,12]
    print(Solution().minInterval(
        intervals=[[54, 82], [55, 66], [81, 89], [38, 67], [81, 86], [47, 47], [13, 61], [33, 39], [61, 66], [97, 97],
                   [52, 68], [96, 98], [89, 92], [1, 41], [81, 89], [9, 57], [81, 90], [41, 73], [29, 80], [98, 98],
                   [61, 95], [93, 98], [5, 65], [91, 96], [91, 99], [28, 68], [55, 71], [35, 45], [1, 89], [48, 48],
                   [26, 36], [5, 83], [20, 83], [73, 92], [69, 69], [77, 89], [12, 52], [5, 53], [33, 53], [70, 83],
                   [81, 98], [69, 69], [28, 90], [9, 77], [40, 53], [53, 71], [7, 55], [7, 28], [5, 88], [61, 68],
                   [25, 93], [45, 73], [13, 51], [27, 70], [47, 87], [71, 91], [93, 98], [1, 35], [24, 39], [86, 90],
                   [19, 33], [1, 69], [21, 100], [85, 85], [99, 99], [25, 25], [90, 94], [13, 61], [69, 85], [89, 97],
                   [1, 43], [11, 35], [41, 95], [31, 99], [86, 94], [33, 63], [22, 91], [61, 75], [71, 83], [31, 85],
                   [28, 83], [1, 21], [81, 97], [5, 29], [74, 83], [33, 83], [13, 24], [92, 94], [71, 71], [59, 79],
                   [21, 37], [33, 87], [97, 97], [34, 57], [11, 59], [57, 62], [22, 23], [13, 53], [84, 85], [71, 80]],
        queries=[31, 9, 21, 91, 91, 58, 13, 76, 21, 69, 41, 1, 73, 2, 71, 51, 69, 89, 31, 85, 61, 61, 39, 76, 36, 50, 1,
                 33, 41, 38, 29, 91, 93, 47, 1, 11, 33, 79, 15, 7, 21, 36, 65, 1, 1, 93, 45, 51, 33, 5, 15, 65, 49, 81,
                 59, 21, 1, 7, 81, 6, 1, 80, 81, 21, 24, 41, 47, 85, 38, 26, 100, 33, 57, 24, 71, 16, 65, 96, 81, 83,
                 17, 75, 76, 21, 85, 47, 77, 49, 31, 61, 9, 49, 1, 73, 32, 66, 96, 97, 30, 21]))
